package com.pkk.penguin.frame.know.java.interview.year2021.atguigu_20210226.algorithm;

import com.alibaba.fastjson.JSONObject;
import java.util.HashMap;
import org.junit.Test;

/**
 * 求和
 *
 * @author peikunkun
 * @version V1.0
 * @date 2021-02-26 14:52
 **/
public class sum {

  /**
   * @return void
   * @Param
   * @author peikunkun
   * @date 2021/2/26 0026 下午 2:52
   * <p>
   * <p>
   * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。
   * <p>
   * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
   * <p>
   * 你可以按任意顺序返回答案。
   * <p>
   *  
   * <p>
   * 示例 1：
   * <p>
   * 输入：nums = [2,7,11,15], target = 9
   * 输出：[0,1]
   * 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
   * 示例 2：
   * <p>
   * 输入：nums = [3,2,4], target = 6
   * 输出：[1,2]
   * 示例 3：
   * <p>
   * 输入：nums = [3,3], target = 6
   * 输出：[0,1]
   * <p>
   * 来源：力扣（LeetCode）
   * 链接：https://leetcode-cn.com/problems/two-sum
   * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
   * </p>
   * @since
   */
  @Test
  public void Administrator_13_20210226145226_() {
    System.out.println("欢迎使用单元测试方法【Administrator_13()_20210226145226】");
    System.out.println("此方法测试描述：【】");

    int source[] = {5, 11, 9, 7, 35};
    int target = 12;
    final int[] ints = sum1(source, target);
    final int[] intsPlus = sumPlus(source, target);
    System.out.println(JSONObject.toJSONString(ints));
    System.out.println(JSONObject.toJSONString(intsPlus));


  }


  /**
   * 最简单的方式
   *
   * @return int[]
   * @Param source
   * @Param target
   * @author peikunkun
   * @date 2021/2/26 0026 下午 3:05
   * @since
   */
  public static int[] sum1(int[] source, int target) {
    //target=source[i]-source[j]   --->>> (j=i+1&&j<=i.length)
    for (int i = 0; i < source.length; i++) {
      for (int j = i + 1; j < source.length; j++) {
        if (source[j] == target - source[i]) {
          return new int[]{i, j};
        }
      }
    }
    return new int[]{};
  }


  /**
   * 这个我们将时间复杂度由O(N^2)降为O(N),这里我们用的是hash直接获取位置
   *
   * @return int[]
   * @Param source
   * @Param target
   * @author peikunkun
   * @date 2021/2/26 0026 下午 4:35
   * @since
   */
  public static int[] sumPlus(int[] source, int target) {
    //依据redis或者map的方式的根据hash直接查找到数据【依据hash】

    final HashMap<Integer, Integer> container = new HashMap<>();
    for (int i = 0; i < source.length; i++) {
      final int j = target - source[i];
      if (container.containsKey(j)) {
        return new int[]{container.get(j), i};
      }
      container.put(source[i], i);
    }
    return new int[]{};
  }


}
